#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

bool ListDelete(LinkList &L, int i, ElemType &e);

int main()
{
    LNode L;
    printf("%p\n", &L);
}

// 最坏和平均时间复杂度 O(n)  最好时间复杂度 O(1)
bool ListDelete(LinkList &L, int i, ElemType &e)
{
    if (i < 1)
        return false;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL)
        return false;
    LNode *q = p->next; // q指向被删除的结点
    e = q->data;        // 返回被删除的元素e
    p->next = q->next;  // 删除q
    free(q);
    return true;
}